package com.ycy.leetcode;

import org.junit.Test;

import java.math.BigInteger;

/**
 * 斐波那契数列
 */
public class Fibonacci {

  @Test
  public void fibonacci() {
    int fnc = fnc(8, 1);
    System.out.println(fnc);
  }

  public int fnc(int i, int depth) {
    System.out.println(depth);
    if (i == 1) return 1;
    if (i == 2) return 2;
    return fnc(i - 1, depth + 1) + fnc(i - 2, depth + 1);
  }


  /**
   * 大数相加，找到第一个达到 1000个数的值， 出现在第几项
   */
  @Test
  public void do1000() {
    BigInteger a = BigInteger.ONE;
    BigInteger b = BigInteger.ONE;

    int num = 2;
    do {
      BigInteger tmp;
      tmp = b;
      BigInteger add = b.add(a);
      b = add;
      a = tmp;
      num++;
    } while (b.toString().length() < 1000);
    System.out.println(num);
    System.out.println(b);
  }

  @Test
  public void main() {
    //f(n) 逆序存放 数值
    int[] before = new int[1000];
    //f(n+1)
    int[] after = new int[1000];

    int[] temp;

    before[0] = after[0] = 1;

    //初始化2项
    int num = 2;

    do {
      temp = after.clone();
      for (int i = 0; i < 1000; i++) {
        after[i] += before[i];
      }
      before = temp;
      for (int i = 0; i < 1000 - 1; i++) {
        //大于十进制，下一个元素进一位
        if (after[i] >= 10) {
          after[i] = after[i] % 10;
          after[i + 1]++;
        }
      }
      num++;
      //第999 != 0 说明可以 位数 达到 1000 ，可以break了;
    } while (after[999] == 0);
    //4782
    System.out.println(num);
  }


}


